One Hundred Prisoners and a Light Bulb by Hans van Ditmarsch & Barteld Kooi
Author:Hans van Ditmarsch & Barteld Kooi
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham
10.2 How to Know Whom to Call
So far, we assumed that the friends can coordinate their actions before making any calls. In the Fixed Schedule protocol for four friends, first Amal calls Bharat, and then Chandra calls Devi, and so on. The way we defined the protocol was that any two friends can make the first call, and then any two other friends can make the second call. So it does not have to be between these exact four individuals. Can the protocol be rephrased such that these scheduling decisions can be made by the friends themselves, when they are about to call someone, and based on what they know? It turns out that this is not possible.
One can still imagine the first two callers be determined randomly. Everybody is dying to make a call, one of the friends is simply getting through before the others in making a call, the recipient of that call can be any other friend. We then assume that the information exchange takes place instantly without consuming time and we can schedule the next call. All friends only know their own secret initially.
But for the second call we now have a problem. After the first call there are two friends who know two secrets, and the remaining friends only know one secret. In other words, they have different knowledge. In order to attempt to copy the Fixed Schedule protocol, we may pick any friend who only knows one secret to initiate the second call; this choice is knowledge-based (and anyone fulfilling the condition can be chosen), and this rules out those who made the first call. This friend now has to call another friend who only knows one secret. But the friend initiating that second call cannot choose such a one-secret-only friend based on his knowledge. If Chandra initiates the second call, and if she is ignorant about who made the first call, then she has no reason to prefer Devi over any other friend. It seems not unreasonable to assume that she only knows that she was not involved herself in that first call. This means that, from Chandra’s point of view, the first call could have been between Amal and Bharat, or between Amal and Devi, or between Bharat and Devi. She does not know which call really happened! A second call between Chandra and Devi has to be “fixed” by an external scheduler (or by the friends themselves, prior to executing the protocol); it cannot be chosen by the friends themselves based on what they learn from receiving calls.
We conclude that it is not possible for the friends themselves to enforce the execution of the Fixed Schedule protocol.
Let us now consider an epistemic protocol wherein a friend calls another friend depending on its knowledge only, and such that any friend fulfilling the knowledge condition is chosen at random.
Protocol 10 (Learn New Secrets) Until all friends know all secrets: choose a friend who does not know all secrets, let this friend choose a friend whose secret he does not know, and make that call.
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Algebra | Calculus |
Combinatorics | Discrete Mathematics |
Finite Mathematics | Fractals |
Functional Analysis | Group Theory |
Logic | Number Theory |
Set Theory |
Modelling of Convective Heat and Mass Transfer in Rotating Flows by Igor V. Shevchuk(6219)
Weapons of Math Destruction by Cathy O'Neil(5823)
Factfulness: Ten Reasons We're Wrong About the World – and Why Things Are Better Than You Think by Hans Rosling(4485)
Descartes' Error by Antonio Damasio(3162)
A Mind For Numbers: How to Excel at Math and Science (Even If You Flunked Algebra) by Barbara Oakley(3102)
Factfulness_Ten Reasons We're Wrong About the World_and Why Things Are Better Than You Think by Hans Rosling(3045)
TCP IP by Todd Lammle(3009)
Applied Predictive Modeling by Max Kuhn & Kjell Johnson(2906)
Fooled by Randomness: The Hidden Role of Chance in Life and in the Markets by Nassim Nicholas Taleb(2855)
The Tyranny of Metrics by Jerry Z. Muller(2844)
The Book of Numbers by Peter Bentley(2779)
The Great Unknown by Marcus du Sautoy(2532)
Once Upon an Algorithm by Martin Erwig(2471)
Easy Algebra Step-by-Step by Sandra Luna McCune(2466)
Lady Luck by Kristen Ashley(2409)
Practical Guide To Principal Component Methods in R (Multivariate Analysis Book 2) by Alboukadel Kassambara(2378)
Police Exams Prep 2018-2019 by Kaplan Test Prep(2354)
All Things Reconsidered by Bill Thompson III(2259)
Linear Time-Invariant Systems, Behaviors and Modules by Ulrich Oberst & Martin Scheicher & Ingrid Scheicher(2230)
